//https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?
//在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增
//的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
            for(int i=0;i<array.size();++i)
            {
                for(int j=array[i].size()-1;j>=0;--j)
                {
                    if(target<array[i][j])
                    {
                        continue;
                    }
                    else if(target==array[i][j]){
                         return true;
                    }
                    else {
                         break;
                    }
                }
            }
            return false;
    }
};
//https://leetcode.cn/problems/add-two-numbers/
//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        int flag = 0; //进位标志
        //采用补0的方式进行
        while (p1 || p2)
        {
            if (p1->next==nullptr && p2->next!=nullptr)
            {
                ListNode* node = new ListNode(0);
                p1->next = node;
            }
            if (p2->next==nullptr && p1->next!=nullptr)
            {
                ListNode* node = new ListNode(0);
                p2->next = node;
            }
            //全部加到p1上
            p1->val = p1->val + p2->val + flag;
            if (p1->val > 9)
            {
                p1->val %= 10;
                flag = 1;
            }
            else
            {
                flag = 0;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        if (flag == 1)
        {
            p1 = l1;
            while (p1->next != nullptr)
            {
                p1 = p1->next;
            }
            ListNode* node = new ListNode(1);
            p1->next = node;
        }

        return l1;
    }
};

//https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?
//输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
#include <any>
#include <vector>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> a;
        while(head)
        {
            a.push_back(head->val);
            head=head->next;
        }

        int n=a.size()-1;
        int i=0;
        while(i<n)
        {
            swap(a[i], a[n]);
            i++;
            n--;
        }
        //reverse(a.begin(), a.end());
        return a;
    }
};
//递归方法
class Solution {
public:
void printListFromTailToHeadCore(ListNode* head, vector<int> &v){
    if(nullptr == head){
        return;
    }
    printListFromTailToHeadCore(head->next, v);
    v.push_back(head->val);
}
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        printListFromTailToHeadCore(head, v);
        return v;
    }
};



//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* p = head;
        ListNode* newhead = head;
        int i=0;
        if(p==nullptr)
        {
            return nullptr;
        }
        while(p->next)
        {
            ++i;
            p=p->next;
        }
        ++i;
        k=k%i;
        k=i-k;
        p->next = head;
        while(k--)
        {
            newhead=newhead->next;
            p=p->next;
        }
        p->next=nullptr;
        return newhead;

    }
};

//